package cxydmmszl.tmp.t13;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.LinkedList;
import java.util.List;

/**
 * <li style="color: red;">Prob</li>
 * 将搜索二叉树转换成双向链表
 * <li style="color: green;">Desc</li>
 * 对二叉树的节点来说，有本身的值域，有指向左孩子节点和右孩子节点的两个指针；
 * 对双向链表的节点来说，有本身的值域，有指向上一个节点和下一个节点的指针。
 * 在结构上，两种结构有相似性，现在有一棵搜索二叉树，请将其转换成一个有序的双向链表。
 * <li style="color: green;">Input</li>
 * 第一行一个数字 n 表示二叉树的总结点数。<br/>
 * 以下 n 行每行三个整数 fa lch rch，表示节点 fa 的左儿子节点为 lch，
 * 右儿子节点为 rch。(若 lch 为 0 则表示 fa 没有左儿子，rch同理) <br/>
 * 第一行的 fa 为根节点。<br/>
 * ps:节点的标号就是节点的值。
 * <li style="color: green;">Output</li>
 * 在给定的函数中返回双向链表的头指针。
 * <li style="color: blue;">Link</li> CD156
 *
 * @author habitplus
 * @since 2021-11-20 12:41
 */
public class Main {

    private static final StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    private static int nextInt() {
        try {
            st.nextToken();
            return (int) st.nval;
        } catch (IOException e) {
            throw new RuntimeException("Input error!");
        }
    }

    static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }
    }

    static class Node {
        int value;
        Node next;
        Node pre;

        public Node(int value) {
            this.value = value;
        }
    }

    /*
        递归创建树，因为给出的数据就是利用递归给出的
     */
    public static TreeNode createTree() throws IOException {

        int value = nextInt();
        int left = nextInt();
        int right = nextInt();
        TreeNode root = new TreeNode(value);

        if (left != 0)
            root.left = createTree();
        if (right != 0)
            root.right = createTree();

        return root;
    }

    /*
        中序遍历 - 得到的就是有序的列表
     */
    /*public static void inOrder(TreeNode root, List<Node> list) {
        if (root == null) {
            return;
        }
        inOrder(root.left, list);
        list.add(new Node(root.value));
        inOrder(root.right, list);
    }*/

    public static void inOrder(TreeNode root, StringBuilder resSb) {
        if (root == null) {
            return;
        }
        inOrder(root.left, resSb);
        resSb.append(root.value).append(" ");
        inOrder(root.right, resSb);
    }

    public static void main(String[] args) throws IOException {
        int n = nextInt();
        TreeNode tree = createTree();
        LinkedList<Node> list = new LinkedList<>();
        StringBuilder resSb = new StringBuilder();
        inOrder(tree, resSb);
//        Node head = new Node(999);
//        Node pre = head;
//        for (Node node : list) {
//            pre.next = node;
//            node.pre = pre;
//            pre = pre.next;
//            sb.append(node.value).append(" ");
//        }

        System.out.println(resSb.toString());
    }
}

